package my.jwds.p2049;

import com.alibaba.fastjson.JSONObject;

public class CountHighestScoreNodes {

    public static void main(String[] args) {
        CountHighestScoreNodes obj = new CountHighestScoreNodes();
        int [] parents = JSONObject.parseObject("[-1,2,0,2,0]",int[].class);
        System.out.println(obj.countHighestScoreNodes(parents));
    }



    public int countHighestScoreNodes(int[] parents) {
        int n = parents.length;
        int[][] nodes = new int[n][2];
        for (int i = 1; i < n; i++) {
            if (nodes[parents[i]][0] == 0){
                nodes[parents[i]][0] = i;
            }else{
                nodes[parents[i]][1] = i;
            }
        }
        int [][] dp = new int[n][2];
        dfs(nodes,dp,0);
        long max = getVal(dp[0][0],dp[0][1]),count = dp[0][1]+dp[0][0]+1;
        int res = 1;
        for (int i = 1; i < n; i++) {
            long num1 = dp[i][0],num2 = dp[i][1],num3 = count-num1-num2-1;
            long temp = getVal(getVal(num1,num2),num3);
            if (temp == max){
                res++;
            }else if (temp > max){
                res=1;
                max = temp;
            }
        }
        return res;
    }


    long getVal(long num1 , long num2){
        return num1 == 0l ? num2 : num2 == 0l? num1 : num1 * num2;
    }

    void dfs(int[][] nodes,int [][] dp,int index){
        if (nodes[index][0] != 0){
            dfs(nodes,dp,nodes[index][0]);
            dp[index][0] = dp[nodes[index][0]][0] + dp[nodes[index][0]][1] + 1;
        }
        
        if (nodes[index][1] != 0){
            dfs(nodes,dp,nodes[index][1]);
            dp[index][1] = dp[nodes[index][1]][0] + dp[nodes[index][1]][1] + 1;
        }
        
    }

}
